#include "DynamicArray.h"
#include<iostream>
using ElementType = int;

DynamicArray::DynamicArray():capacity(10),size(0)
{
    this->a = new ElementType[capacity];
}

DynamicArray::DynamicArray(const DynamicArray &array)
{
    this->size = array.size;
    this->capacity = array.capacity;
    this->a = new ElementType[capacity];
    for(int i=0;i < this->size; i++)
    {
        this->a[i] = array.a[i];
    }
}

void DynamicArray::operator=(const DynamicArray &array)
{
    this->size = array.size;
    this->capacity = array.capacity;
    for(int i=0;i < this->size; i++)
    {
        this->a[i] = array.a[i];
    } 
}

DynamicArray::~DynamicArray()
{
    delete []a;
}

void DynamicArray::InsertTail(const ElementType &element)
{
    if(size >= capacity)
    {
        capacity *=2;
        ElementType *newptr = new ElementType[capacity];
        for(int i=0;i<size;i++)
        {
            newptr[i] = a[i];
        }
        delete []a;
        a = newptr;
    }
    a[size++] = element;
}

int DynamicArray::FindByElement( ElementType element)
{
    for(int i=0;i<this->size;i++)
    {
        if(this->a[i] == element)
            return i;
        else
            std::cout<<"没有找到!"<<std::endl;
            return 0;
    }
    return 0;
}

void DynamicArray::RemovrByIndex(ElementType Index)
{
    if(Index < 0 || Index >= this->size)
    {
        std::cout<<"无法删除这个位置的数!"<<std::endl;
        return;
    }
    for (int i = Index; i < this->size; i++)
    {
        this->a[i] = this->a[i+1];       
    }
    this->size--;

    
}

void DynamicArray::RemovrByElement(ElementType element)
{
    for(int i=0;i<this->size;i++)
    {
        if(this->a[i] == element)
        {
            RemovrByIndex(i);
            i--;
        }
    }
}





void DynamicArray::FastSort( int start, int end)
{
    if(start >= end)
    {
        return;
    }

    int left = start;
    int right = end;

    ElementType temp = this->a[left];

    while( left < right )
    {
        while(this->a[right] > temp && left < right)
                    right--;
        if(left < right)
        {
            this->a[left] = this->a[right];
            left++;
        }

        while(this->a[left] < temp && left<right)
                    left++;
        if(left < right)
        {
            this->a[right] = this->a[left];
            right--;
        }
        
    }
    this->a[left] = temp; 
    
    FastSort(start,left - 1);
    FastSort(right+1,end);

}

ElementType DynamicArray::BinarySearch(ElementType element)
{
    int left = 0;
    int right = this->size -1;
    while(left <= right)
    {
        // int mid = left + (right - left) / 2;
        int mid = (left & right) +((left ^ right) >> 1);
        
        if(this->a[mid]>element)
        {
            right = mid -1;
        }
        else if(this->a[mid]<element)
        {
            left = mid +1;
        }
        else
            return mid;
    }
    return -1;
}



void DynamicArray::show()
{
    for (int i = 0; i < size; i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
}
